﻿#pragma once
#include<iostream>

using namespace std;

enum color
{
	RED,
	BLACK
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode()
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)
	{}
	RBTreeNode(const K& key, const V& val)
		:_val(val),
		_key(key),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)
	{}

	bool is_leaf()
	{
		if (_left || _right)
			return false;

		return true;
	}

	K _key;
	V _val;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	color _col;
};

template<class K,class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	enum direction
	{
		LEFT,
		RIGHT
	};
	RBTree()
	{
		_pHead = new Node;
		_pHead->_left = _pHead;
		_pHead->_right = _pHead;
		_pHead->_col = BLACK;
	}

	~RBTree()
	{
		if (_pHead->_left == _pHead)
		{
			delete _pHead;
		}
		else
		{
			_Destroy(_pHead->_left);
			delete _pHead;
		}
	}

	bool insert(const K& key,const V& val)
	{
		if (_pHead->_left == _pHead)
		{
			Node* ins = new Node(key, val);
			ins->_col = BLACK;

			_pHead->_left = _pHead->_right = ins;
			ins->_parent = _pHead;
			return true;
		}

		Node* cur = _pHead->_left;
		Node* parent = _pHead;
		direction dir;

		while (cur)
		{
			if (cur->_key == key)
				return false;
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
				dir = RIGHT;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
				dir = LEFT;
			}
		}

		cur = new Node(key, val);
		cur->_parent = parent;
		if (dir == RIGHT)
			parent->_right = cur;
		else if (dir == LEFT)
			parent->_left = cur;

		while (cur)
		{
			if (parent->_col == BLACK)
				break;

			else if (parent->_col == RED)
			{
				Node* uncle = get_uncle(cur);
				Node* grandparent = parent->_parent;

				if (uncle == nullptr|| uncle->_col == BLACK)
				{
					//如果uncle为空  则说明只有一种情况：
					//cur就是叶子节点
					//而uncle为黑和uncle为空处理情况是一样的：旋转加变色

					//三点一线的情况：单旋
					if (grandparent->_left == parent && parent->_left == cur)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = cur->_col = RED;
					}
					else if (grandparent->_right == parent && parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = cur->_col = RED;
					}

					//三点不共线的情况：双旋
					else if (grandparent->_left == parent && parent->_right == cur)
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = parent->_col = RED;
					}
					else if (grandparent->_right == parent && parent->_left == cur)
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = parent->_col = RED;
					}

					break;
				}
				else if (uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
					parent = cur->_parent;
					continue;
				}
			}
		}

		_pHead->_left->_col = BLACK;
		_pHead->_col = BLACK;
		return true;
	}

	void Inorder()
	{
		_Inorder(_pHead->_left);
		cout << endl;
	}

	bool is_balance()
	{
		if (_pHead->_left == _pHead)
			return true;

		Node* cur = _pHead->_left;
		int adjust = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
				adjust++;
			cur = cur->_left;
		}

		return _is_blance(_pHead->_left, 0, adjust);
	}

	Node* find(const K& key)
	{
		if (_pHead->_left == _pHead)
			return nullptr;

		return _find(_pHead->_left,key);
	}

	Node* LeftMost()
	{
		if (_pHead->_left == _pHead)
			return nullptr;

		Node* parent = _pHead;
		Node* cur = _pHead->_left;
		
		while (cur)
		{
			parent = cur;
			cur = cur->_left;
		}

		return parent;
	}

	Node* RightMost()
	{
		if (_pHead->_left == _pHead)
			return nullptr;

		Node* parent = _pHead;
		Node* cur = _pHead->_left;

		while (cur)
		{
			parent = cur;
			cur = cur->_right;
		}

		return parent;
	}
private:
	Node* _pHead;

	void _Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

	Node* get_uncle(Node* root)
	{
		Node* parent = root->_parent;
		Node* grandparent = parent->_parent;
		if (!grandparent||grandparent==_pHead)
			return nullptr;

		if (grandparent->_left == parent)
			return grandparent->_right;
		else if (grandparent->_right == parent)
			return grandparent->_left;
	}

	void RotateR(Node* root)
	{
		Node* grandparent = root->_parent;
		Node* parent = root;
		Node* cur = root->_left;
		//Node* childL = cur->_left;
		Node* childR = cur->_right;

		if (grandparent == _pHead)
		{
			_pHead->_left = _pHead->_right = cur;
		}
		else 
		{
			if (grandparent->_left == root)
			{
				grandparent->_left = cur;
			}
			else if (grandparent->_right == root)
			{
				grandparent->_right = cur;
			}
		}
		cur->_parent = grandparent;
		cur->_right = parent;

		parent->_parent = cur;
		parent->_left = childR;

		if (childR)
			childR->_parent = parent;
	}

	void RotateL(Node* root)
	{
		Node* grandparent = root->_parent;
		Node* parent = root;
		Node* cur = root->_right;
		Node* childL = cur->_left;
		//Node* childR = cur->_right;

		if (grandparent == _pHead)
		{
			_pHead->_left = _pHead->_right = cur;
		}
		else
		{
			if (grandparent->_left == root)
			{
				grandparent->_left = cur;
			}
			else if (grandparent->_right == root)
			{
				grandparent->_right = cur;
			}
		}

		cur->_parent = grandparent;
		cur->_left = parent;

		parent->_parent = cur;
		parent->_right = childL;

		if (childL)
			childL->_parent = parent;
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_key << ' ';
		_Inorder(root->_right);
	}

	size_t Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		size_t left = Height(root->_left);
		size_t right = Height(root->_right);

		return Max(left, right) + 1;
	}

	bool _is_blance(Node* root,int i,const int adjust)
	{
		if (root == nullptr && i == adjust)
			return true;

		if (root->_col == RED && root->_parent->_col == RED)
			return false;

		if (root->_col == BLACK)
			i++;

		return _is_blance(root->_left, i, adjust)&&_is_blance(root->_right,i,adjust);
	}

	Node* _find(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_key == key)
		{
			return root;
		}
		else if (root->_key > key)
		{
			return _find(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _find(root->_right, key);
		}
	}
};